package leetcode.editor.cn.q1_300.q;

/**
 * 知道是动态规划，但是没想通。。。
 * 看了答案，还没看懂。。。做到 100 题了回来再看的
 * 看了评论，懂了。。。但是分析不出来。。。还是抄了答案
 *
 * @author qidi
 * @date 2022-01-04 09:19:28
 */
class Q0010_RegularExpressionMatching {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true;

            for (int i = 0; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (p.charAt(j - 1) == '*') {
                        // 这里 j-2 是默认 * 是 0 个，需要 【#*】之前的字符匹配状态
                        dp[i][j] = dp[i][j - 2];
                        if (match(s, p, i, j - 1)) {
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                        }
                    } else {
                        if (match(s, p, i, j)) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                }
            }

            return dp[m][n];
        }

        private boolean match(String s, String p, int i, int j) {
            if (i == 0) return false;

            if (p.charAt(j - 1) == '.') return true;

            return p.charAt(j - 1) == s.charAt(i - 1);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0010_RegularExpressionMatching().new Solution();
    }
}